跳表 Skip List 的基本概念

跳表的原始表就是一个普通的链表，查找元素的时间复杂度为 O(N), 可以先看图中的原始表一行，其它先不管。那么查找117元素就要找8次才可以，如果这个链表超长的话当然时间也就会越多，这就体现出跳表的优点来。

原始表生成跳表的方法是提取索引，第一是相隔一定个数后提取出跳表索引第0层，也就是
7 -> 21 -> 37 -> 71

然后再根据第0层提取出第一层来。那么我们的top 指针也指向最高层的链表的头结点，也就是图中 跳表第1层的最左端。这里的提取密度和层数根据需要，当然还有一些说法，这里不讲，只说基本概念。

那么我们再查找117就简单了，先比较第1层的第一个元素，37 < 117，再找37下一个元素，没有，跳到 下一层的37的下一个元素71，71 > 117，再跳到下一层，也就是最原始层71的下一个元素85。 85 <117 ,再下一个，找到了。

相应查找的算法为：

p=top
While(1){
    while (p->next->key < x ) p=p->next;
    If (p->down == NULL ) return p->next
    p=p->down ;
}

总结
跳表的构造过程是：
给定一个有序的链表。
选择连表中最大和最小的元素，然后从其他元素中按照一定算法随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。
为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
重复2、3步，直到不再能选择出除最大最小元素以外的元素。

跳表的特征：
一个跳表应该有几个层（level）组成；
跳表的第一层包含所有的元素；
每一层都是一个有序的链表；
如果元素x出现在第i层，则所有比i小的层都包含x；
第i层的元素通过一个down指针指向下一层拥有相同值的元素；
在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)；
Top指针指向最高层的第一个元素。

赏

谢谢你请我吃糖果